
package shujujiegou;
import java.util.Scanner;
import java.util.Arrays;

class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

public class lianbiao {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("请输入链表1的节点个数:");

        int n = input.nextInt();
        Node list1 = createList(input, n, "链表1");

        System.out.print("请输入链表2的节点个数");
        int m = input.nextInt();
        Node list2 = createList(input, m, "链表2");
        System.out.print("\n链表1：");
        printList(list1);
        System.out.print("链表2：");
        printList(list2);

        System.out.println("\n【链表方式】");
        Node mergedList = mergeByList(list1, list2);
        System.out.print("合并结果（正序）：");
        printList(mergedList);

        Node reversedList = reverseList(mergedList);
        System.out.print("合并结果（逆序）：");
        printList(reversedList);

        System.out.println("\n【数组方式】");
        int[] arr1 = listToArray(list1, n);
        int[] arr2 = listToArray(list2, m);
        int[] mergedArr = mergeByArray(arr1, arr2);

        System.out.println("合并结果（正序）：" + Arrays.toString(mergedArr));

        int[] reversedArr = reverseArray(mergedArr);
        System.out.println("合并结果（逆序）：" + Arrays.toString(reversedArr));

        input.close();
    }


    static Node createList(Scanner input, int size, String name) {
        if (size == 0) return null;

        System.out.print("输入" + name + "的第1个值：");
        Node head = new Node(input.nextInt());
        Node current = head;

        for (int i = 1; i < size; i++) {
            System.out.print("输入" + name + "的第" + (i + 1) + "个值：");
            current.next = new Node(input.nextInt());
            current = current.next;
        }
        return head;
    }

    static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println("->nullptr");
    }

    static Node mergeByList(Node a, Node b) {
        Node dummy = new Node(0);
        Node tail = dummy;

        while (a != null && b != null) {
            if (a.value <= b.value) {
                tail.next = new Node(a.value);
                a = a.next;
            } else {
                tail.next = new Node(b.value);
                b = b.next;
            }
            tail = tail.next;
        }

        tail.next = (a != null) ? a : b;
        return dummy.next;
    }

    static Node reverseList(Node head) {
        Node prev = null;
        while (head != null) {
            Node next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static int[] listToArray(Node head, int size) {
        int[] arr = new int[size];
        for (int i = 0; i < size && head != null; i++) {
            arr[i] = head.value;
            head = head.next;
        }
        return arr;
    }

    static int[] mergeByArray(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;

        while (i < a.length && j < b.length) {
            result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
        }

        while (i < a.length) result[k++] = a[i++];
        while (j < b.length) result[k++] = b[j++];

        return result;
    }

    static int[] reverseArray(int[] arr) {
        int[] reversed = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            reversed[i] = arr[arr.length - 1 - i];
        }
        return reversed;
    }
}